﻿//137.只出现一次的数II
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++)
        {
            int count = 0;
            for (int j = 0; j < nums.size(); j++)
            {
                count += ((nums[j] >> i) & 1);
            }
            if (count % 3 != 0)
            {
                ans |= (1 << i);
            }
        }
        return ans;
    }
};


//面试题 17.19.消失的两个数字
class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size(), sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum ^= nums[i];
        }

        for (int i = 0; i < n + 2; i++)
        {
            sum ^= (i + 1);
        }

        int pos = 0;
        for (int i = 0; i < 32; i++)
        {
            if (((sum >> i) & 1) == 1)
            {
                pos = i;
                break;
            }
        }

        int ans1 = 0, ans2 = 0;
        for (int i = 0; i < n; i++)
        {
            if (((nums[i] >> pos) & 1) == 1)
            {
                ans1 ^= nums[i];
            }
            else
            {
                ans2 ^= nums[i];
            }
        }
        for (int i = 0; i < n + 2; i++)
        {
            if ((((i + 1) >> pos) & 1) == 1)
            {
                ans1 ^= (i + 1);
            }
            else
            {
                ans2 ^= (i + 1);
            }
        }

        return { ans1, ans2 };
    }
};

//面试题 17.16.按摩师
class Solution {
public:
    int massage(vector<int>& nums) {
        int n = nums.size();

        if (n == 0) return 0;

        vector<int> f(n), g(n);
        f[0] = nums[0];

        for (int i = 1; i < n; i++)
        {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }

        return max(f[n - 1], g[n - 1]);
    }
};

